package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func dp(root *TreeNode) (int, int) {
	if root == nil {
		return 0, 0
	}
	incLeft, excLeft := dp(root.Left)
	incRight, excRight := dp(root.Right)
	inc := root.Val + excLeft + excRight
	exc := incLeft + incRight
	inc = max(inc, exc)
	return inc, exc
}

func rob(root *TreeNode) int {
	inc, exc := dp(root)
	return max(inc, exc)
}

func main() {
	root := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 2,
			Right: &TreeNode{
				Val: 3,
			},
		},
		Right: &TreeNode{
			Val: 3,
			Right: &TreeNode{
				Val: 1,
			},
		},
	}
	println(rob(root))
}
